\documentclass[11pt,letterpaper]{article}

\newcommand{\mytitle}{CS254 Homework 2}
\newcommand{\myauthor}{Kevin Lewi}
\date{January 27, 2011}

\usepackage{hwformat}

\begin{document}

\maketitle

\section*{Problem 1}

\section*{Problem 2}

We prove the contrapositive. Suppose $L \in NP$ and $L \not\in P$. We will 
construct an $L'$ and show that it lies in $MajorityP$. Let $M_1$ be the 
nondeterministic machine that accepts $L$.

Since $L \in NP$, there is a witness $w$ of length $z$ such that $M_1(x,w)$ 
accepts when $x \in L$.

Now, we construct a language $L'$ and a probabilistic machine $M_2$ that uses 
$z+1$ bits of randomness. $M_2(x,r)$ will automatically accept if the first bit 
of $r$ is a $1$. On the other hand, if the first bit of $r$ is a $0$, then 
$M_2(x,r)$ accepts if and only if the remaining bits of $r$ are equivalent to 
the witness $w$ such that $M_1(x,w)$ accepts for $x \in L$. Note now that if $x 
\in L$, there are at least $2^{z} + 1$ strings $r$ that cause $M_2$ to accept. 
There are only $2^{z+1}$ strings of length $z+1$, so the probability that $M_2$ 
accepts when $x \in L'$ is greater than $1/2$.

Now, when $x \not\in L'$, if the first bit of $r$ is a $0$, then there is no way 
that $M_2$ will accept $x$, since there are no witnesses for $x \not\in L$ such 
that $M_1$ accepts $x$. Thus, $M_2$ will only accept if the first bit of $r$ is 
a $1$, which happens $1/2$ of the time. Therefore, we can conclude that if $x 
\not\in L$, then the probability that $M_2(x,r)$ accepts is $1/2$.

Therefore, we can conclude that $L' \in MajorityP$ by definition. It remains to 
prove that $L' \not\in P$. Assume for the sake of contradiction that $L' \in P$, 
and $M_3$ is the deterministic machine that accepts $L'$. Note that the input 
space between $L'$ and $L$ are the same, so $M_3$ would also accept $L$. But 
this contradicts our assumption that $L \not\in P$. This contradiction 
establishes the desired claim: that if $P \neq NP$, then $P \neq MajorityP$. 
Thus, if $P = MajorityP$, then $P = NP$.

\section*{Problem 3}

Consider the following language $L$ that takes as input a triple $(x,y,z)$, 
where $(x,y,z) \in L$ if and only if the first $100$ bits of $A(x,y)$ are equal 
to $z$ (here, $A(x,y)$ refers to the Ackermann-Peter function).

Note that computing $A(x,y)$ takes time exponential in the length of the input 
simply due to the number of recursive steps. Also, there exists a 
polynomial-sized circuit that represents the function $f$, where $f(x,y)$ is the 
first $100$ bits of $A(x,y)$.

Thus, we can construct a machine $M$ that, on input $(x,y,z)$ simply queries the 
circuit (or, ``advice string'') to get $f(x,y)$. Then, $M$ simply checks 
$f(x,y)$ against $z$ and accepts if and only if they are equal. Thus, $L \in 
P/poly$.

However, $L \not\in P$, since as stated above, in order to compute $A(x,y)$, one 
must take at least an exponential of recursive steps.


\end{document}
